1. Field of the Invention
The invention concerns binary multiplication, least significant bit first, of a multiplicand by a multiplier coefficient within a multiplier, especially but not exclusively a serial bit multiplier in which the bits of the multiplicand are fed serially to the multiplier input.
2. Description of the Prior Art
Binary multiplication, least significant bit first, of a multiplicand by a multiplier coefficient involves determining, for each bit of the multiplier coefficient after the least significant bit, sums obtained from partial products of said bit in question with the n bits of the multiplicand and from the corresponding sums associated with the preceding bit(s) of the multiplier coefficient.
These sums are calculated in adders which allow for the carries resulting from these operations. The man skilled in the art knows that, generally speaking, given the potential for carries the addition of two numbers on n bits can produce a number on b+1 bits so that it is necessary to take into account for each bit in question of the multiplier coefficient the sum of rank n+1 to be used to calculate some later sums associated with subsequent bits of the multiplier coefficient.
Serial bit multipliers usually operate with a constant dynamic range, i.e. for a multiplicand on n bits only n bits are produced at the output of each adder and at the output of the multiplier.
One solution is then to calculate only n bits in each adder. However, it is then necessary to ensure that the result fits into n bits in order to avoid the problems of internal overflow at intermediate sections in a serial bit multiplier, which could give an erroneous final result.
A solution of this kind is described in the article "Two's Complement Pipeline Multipliers" by R. F. LYON, IEEE Transactions on Communications, April 1976, pages 418-425. This solution has been implemented in a serial bit multiplier which duplicates the sign bit of the operands. This article shows that if the most significant bit of the multiplicand is duplicated (this is the sign bit as the binary number is a signed number in two's complement arithmetic), the various sums of rank n+1 are equal to the sums of rank n calculated, which amounts to saying that the result of each addition fits into n bits. Consequently, in each intermediate section of the multiplier the sum of rank n is merely duplicated to obtain without calculation the sum of rank n+1.
However, a solution of this kind requires the use of an additional bit in the data, which can carry a heavy penalty in the case of highly multiplexed filters. Also, this constraint in respect of the data makes it difficult to model the behaviour of the multiplier in the event of internal overflow, because of non-conformance with duplication of the most significant bit (sign bit) of the multiplicand at the multiplier input; it can cause major stability problems if the multiplier is used to implement recursive filters.
The invention is directed to providing a solution to this problem.
An object of this invention is to enable the use of two's complement coded data without duplication of the sign bit and in particular to propose a serial bit multiplier whose behavior conforms in all respects to the requirements of two's complement arithmetic.